#include"LinkList.h"
#include<iostream>

LinkList::LinkList():size(0)
{
    head= new Node(0);
}

LinkList::LinkList(const LinkList &list)
{
    size=list.size;
    head=new Node(0);
    Node *tp=head;
    Node *travePoint=list.head->next;
    while(travePoint!=nullptr)
    {
        Node *newNode=new Node(travePoint->value);
        tp->next=newNode;
        tp=tp->next;
        travePoint=travePoint->next;
    }


}

LinkList &LinkList::operator=(const LinkList &list)
{
        while(head!=nullptr)
    {
        Node *nextNode=head->next;//下个节点存下
        delete head;
        head=nextNode;
    } 
    size=list.size;
    head=new Node(0);
    Node *tp=head;
    Node *travePoint=list.head->next;
    while(travePoint!=nullptr)
    {
        Node *newNode=new Node(travePoint->value);
        tp->next=newNode;
        tp=tp->next;
        travePoint=travePoint->next;
    }  
    return *this;
}

LinkList::~LinkList()
{
    //遍历从头开始释放
    while(head!=nullptr)
    {
        Node *nextNode=head->next;//下个节点存下
        delete head;
        head=nextNode;
    }
}

void LinkList::InsertTail(const ElementType &element)//O(n)
{
        //遍历指针
        Node *travePoint=head;
        while(travePoint->next!=nullptr)//还没到尾部
            travePoint=travePoint->next;
        Node *newNode=new Node(element);//创建一个新的节点
        travePoint->next=newNode;
        size++;
}

void LinkList::InsertHead(const ElementType &element)//O(1)
{
    Node *newNode=new Node(element);//创建一个新节点
    newNode->next=head->next;
    head->next=newNode;//插入节点
    size++;
}

void LinkList::InsertByindex(size_t index,const  ElementType &element)
{
    if(index>size)
    {
        std::cout<<"位置非法！\n";
        return;
    }
    Node *travePoint=head;//head-index，落到index-1位置
    for(size_t i=0;i<index;i++)
    {
        travePoint=travePoint->next;
    }
    Node *newNode=new Node(element);
    newNode->next=travePoint->next;//新插入节点后接原index节点
    travePoint->next=newNode;//原index-1节点后插新节点
    size++;
}

void LinkList::RemoveByindex(size_t index)//O(n)
{
     if(index>size)
    {
        std::cout<<"位置非法！\n";
        return;
    }
    Node *travePoint=head;
    for(size_t i=0;i<index;i++)
    {
        travePoint=travePoint->next;
    }
    Node *freeNode=travePoint->next;//待释放指针
    travePoint->next=freeNode->next;//把index-1节点的next指针指向index+1节点
    delete freeNode;
    size--;

}

void LinkList::RemoveByelement(const ElementType &element)//O(n)
{
    Node *travePoint=head;
    while(travePoint->next!=nullptr)//遍历
    {
        if(travePoint->next->value==element)//找到待删除元素
        {
            Node *freeNode=travePoint->next;
            travePoint->next=freeNode->next;
            delete freeNode;
            size--;
        }
        else
            travePoint=travePoint->next;//没找到，指针指向下一个节点，找到，原地踏步，下次删除就不会跳一个
    }
}

ElementType *LinkList::FindByIndex(size_t index)//O(n)
{
      if(index>=size)
    {   
        return  nullptr;
    }
    Node *travePoint=head->next;//head->next-index，落到index位置
    for(size_t i=0;i<index;i++)
    {
        travePoint=travePoint->next;
    }
        return &travePoint->value;

    
}

DArray::DynamicArray LinkList::FindElement(const ElementType &element)
{
    DArray:: DynamicArray array;
    Node *travePoint=head->next;
    while(travePoint!=nullptr)
    {
        if(travePoint->value==element)
            array.Inserttail(&travePoint->value);
        
        travePoint=travePoint->next;
    }
        return array; 

}

void LinkList::UpdateByindex(size_t index, const ElementType &elelment)//O(n)
{
       if(index>=size)
    {
        std::cout<<"位置非法！\n";
        return;
    }
    Node *travePoint=head->next;
    for(size_t i=0;i<index;i++)
    {
        travePoint=travePoint->next;
    }
    travePoint->value=elelment;
}

void LinkList::UpdateByElement(const ElementType &oldvalue, const ElementType &newvalue)
{
    Node *travePoint=head->next;
    while(travePoint!=nullptr)
    {
        if(travePoint->value==oldvalue)
                travePoint->value=newvalue;
        
        travePoint=travePoint->next;
    }
}

void LinkList::BubbleSort()
{
   
    for(size_t i=0;i<size-1;i++)
    {
        Node *travePoint=head;//每次循环都回到链表的开头
        for(size_t j=0;j<size-1-i;j++)
        {
            if(travePoint->next->value>travePoint->next->next->value)
            {
                //定义两个节点
                Node *prev=travePoint->next;
                Node *back=travePoint->next->next;
                prev->next=back->next;//先修改第一个节点，修改第二个节点会导致后面节点丢失
                back->next=prev;
                travePoint->next=back;
            }
            travePoint=travePoint->next;//跳转下一个节点，继续判
        }
    }
}

void LinkList::Sort()
{
    FastSort(head->next,nullptr);
}

ElementType *LinkList::GetReserveIndex(size_t index)
{
    //用快慢指针   
       if(index>=size)
    {
        std::cout<<"位置非法！\n";
        return nullptr;
    }
    Node *slow=head->next;
    Node *fast=head;
    for(size_t i=0;i<index;i++)
    {
        fast=fast->next;
    }
    while(fast->next!=nullptr)
    {
        fast=fast->next;
        slow=slow->next;
    }
    return &slow->value;
}

LinkList LinkList::Merge(const LinkList &list)
{
   LinkList result;
   Node *first=head->next;
   Node *Second=list.head->next;
   while(first&&Second)
   {
        if(first->value<Second->value)
        {
            result.InsertTail(first->value);
            first=first->next;
        }
        else
        {
            result.InsertTail(Second->value);
            Second=Second->next;
        }
   }
   while(first)
   {
            result.InsertTail(first->value);
            first=first->next;
   }
   while(Second)
   {
            result.InsertTail(Second->value);
            Second=Second->next;
   }
   return result;
}

void LinkList::Reserve()
{
    Node *prev=nullptr;
    Node *cur=head->next;
    Node *Next=cur->next;
    while(Next!=nullptr)
    {
        cur->next=prev;//逆序
        prev=cur;
        cur=Next;
        Next=cur->next;
    }
    cur->next=prev;//最后一个节点
    head->next=cur;
}

void LinkList::Reserve2()
{
    head->next=reserve(head->next);

}

void LinkList::show()
{
    std::cout<<"size: "<<size<<std::endl;
    Node *travePoint=head->next;
    while(travePoint!=nullptr)//还没有结束
    {
            std::cout<<travePoint->value<<" ";
            travePoint=travePoint->next;//遍历指针往后走
    }
    std::cout<<std::endl;
}

void LinkList::FastSort(Node *start, Node *end)
{   
    //快慢指针法
    //终止条件
    if(start==end)
        return;
    Node *temp=start;//基准值指针
    Node *slow=start;
    Node *fast=start->next;
    while(fast!=end)//快指针没有到结尾
    {
        //快指针指向的值比基准值小
        if(fast->value<temp->value)
        {
            slow=slow->next;
            std::swap(slow->value,fast->value);//交换快慢指针的值
        }
        fast=fast->next;
    }
    std::swap(temp->value,slow->value);//将基准值归位
     FastSort(start,slow);//[start,slow)
      FastSort(slow->next,end);
    

}

LinkList:: Node *LinkList::reserve(Node *node)
{
   //返回值是原来的尾巴，新链表的头
    if(node->next==nullptr)//这个节点是尾巴，逆序完的头
        return node;
    else
    {
        Node *newHead=reserve(node->next);//递归往后走
        //逆序核心
        node->next->next=node;
        node->next=nullptr;//新尾巴 原来的头 指针指向空
        return newHead;
    }   
}
